/**
**********************************************************************
* @file     signal_link_list.c
* @brief    单向链表的实现
* @details
* 本文件中简要介绍了单向链表的结构和用法。并且实现了对单向链表的操作的函数。
* @author   CaiJing
* @date     2021-05-11 08:48:27
* @copyright Copyright &copy; 2021 wy1107412334@163.com All rights reserved
* @version  v0.0.10
*
* \n Email:  wy1107412334@163.com
* \n Blog:   None
* \n Github: https://github.com/wy1107412334
* \n Gitee:  https://gitee.com/git.git1107412334.com
*
**********************************************************************
* @note
*
* 链表简介
* =======
*
* 1. 本链表是一个单向链表。从链表头节点一直向后指，一直可以指到尾结点。
* 2. 本链表有一个链表表头和若干个链表节点。
*   - 链表表头用于表示一个链表。其中保存了链表的头节点和尾节点的地址。
* 3. 空链表的表头的 head 和 tail 元素的值为 NULL。
* 4. 非空链表的尾节点的 next 元素的值为 NULL。
*
*
* 链表使用
* =======
* 1. 数据类型 SL_NODE 需要放在用户自定义的struct的最开头，
*    这样链表节点的地址也就是用户自定义的struct的首地址。
*    这样方便通过本链表返回的节点地址来处理用户自定义的数据:\n
*    @code
*    struct abc {
*        SL_NODE node;
*        // 用户定义的数据类型字段
*    };
*    @endcode
* 2. 先创建并初始化一个链表的表头，可以使用如下两种方式：
*   - 定义 SL_LIST 类型变量，然后将变量的地址传递给函数 sllist_static_init()
*   - 定义 SL_LIST * 类型变量保存函数 sllist_alloc_init() 的返回值
* 3. 对上面初始化的链表进行操作。
*
**********************************************************************
* @attention
* None.
**********************************************************************
@verbatim

=====================================
        单向链表的内存布局图
=====================================

空链表
=====

链表头：
+------+------+
| head | NULL |
+------+------+
| tail | NULL |
+------+------+


存在一个节点的链表
=================

链表头：               节点
+------+         +---->+------+------+
| head |---------+     | next | NULL |
+------+         |     +------+------+
| tail |---------+
+------+


存在两个节点的链表
=================

链表头：               节点1                节点2
+------+         +---> +------+      +----> +------+------+
| head |---------+     | next |------+      | next | NULL |
+------+               +------+      |      +------+------+
| tail |-----------------------------+
+------+


存在三个节点的链表
=================

链表头：               节点1          节点2             节点3
+------+         +---> +------+  +--> +----- +   +----> +------+------+
| head |---------+     | next |--+    | next |---+      | next | NULL |
+------+               +------+       +------+   |      +------+------+
| tail |-----------------------------------------+
+------+


使用链表节点的数据类型
=====================

struct abc {
    SL_NODE    node;
    int        val;
};

链表头：               节点1          节点2             节点3
+------+         +---> +------+  +--> +----- +   +----> +------+------+
| head |---------+     | next |--+    | next |---+      | next | NULL |
+------+               +------+       +------+   |      +------+------+
| tail |---------+     | val  |       | val  |   |      | val  |
+------+         |     +------+       +------+   |      +------+
                 +-------------------------------+

@endverbatim
**********************************************************************
* @par 历史记录
*  1. V0.0.1: caijing，2021-05-11 08:48:27
*    - 首次编写
*  2. V0.0.2: jcai, 2021年5月16日 21点32分
*    - 新增清空链表的函数
*  3. V0.0.3: jcai, 2021年5月17日 09点17分
*    - 修复链表排序函数丢失节点的错误
*    - 新增从链表指定节点之后插入节点的函数
*    - 新增以节点首地址转换为节点索引的函数
*    - 删除行末多余空白字符
*    - 删除多余头文件
*  4. V0.0.4: jcai, 2021年5月18日 18点32分
*    - 优化排序函数
*  5. V0.0.5: jcai, 2021年5月18日 20点48分
*    - 修改文件头注释
*  6. V0.0.6: jcai, 2021年5月19日 19点07分
*    - 修改寻找链表中指定节点的函数及其回调函数的参数表
*  7. V0.0.7: jcai, 2021年5月24日 19点13分
*    - 增加函数 sllist_deleteAt(), sllist_inversion()
*    - 使用枚举值替代函数返回的错误码
*  8. V0.0.8: jcai, 2021年6月29日 02点02分
*    - 新增销毁链表的函数
*    - 修复注释问题
*  9. V0.0.9: jcai, 2021年7月9日 14点02分
*    - 修改统计链表长度的方式
*    - 修改doxygen注释格式
*  10. v0.0.10: jcai, 2021年8月3日 10点24分
*    - 完善doxygen注释格式
*
*<center>Copyright &copy; 2021 wy1107412334@163.com All rights reserved</center>
**********************************************************************
*/

/* 头文件导入区 ----------------------------------------------------*/

#include <stdlib.h>
#include "signal_link_list.h"



/** @defgroup SIGNAL_LINK_LIST SIGNAL_LINK_LIST
 * @brief 单向链表模块
 * @{
 */



/*********************************************************************
                私有宏定义
*********************************************************************/






/*********************************************************************
                私有数据类型声明
*********************************************************************/








/*********************************************************************
                私有变量定义
*********************************************************************/





/** @defgroup SIGNAL_LINK_LIST_Exported_Variables signal link list exported variables
 * @brief 全局变量定义
 * @{
 */



/** defgroup SIGNAL_LINK_LIST_Exported_Variables
 * @}
 */





/*********************************************************************
                私有函数定义
*********************************************************************/












/** @defgroup SIGNAL_LINK_LIST_Exported_Functions signal link list exported functions
 * @brief 全局函数定义
 * @{
 */



/**
 * @brief    动态申请并初始化链表头
 * @details
 * 本函数先动态申请一块保存链表头的内存空间，然后初始化该链表，
 * 最后返回链表头的地址。
 * @param   none
 * @return  成功，返回已初始化的链表头的地址；失败，返回NULL
 * @note
 * 在不使用本函数创建的链表时，需要调用函数 sllist_free()
 * 来释放链表头占用的空间；或者说也可以直接调用函数 free()
 * 来释放本函数创建的链表头占用的内存空间。
 * @see sllist_free(), sllist_static_init()
 */
SL_LIST * sllist_alloc_init(void)
{
    SL_LIST * sl;

    sl = (SL_LIST *)malloc(sizeof(SL_LIST));
    sllist_static_init(sl);
    return sl;
}

/**
 * @brief   释放动态申请的链表头
 * @details 释放动态申请的链表头
 * @param [in] sl: 指向链表头的指针
 * @retval 0:  成功
 * @retval SL_ERR_ARGS: 参数 sl 为NULL
 * @retval SL_ERR_NOTEMPTY: 链表 sl 非空
 * @note
 * 链表 sl 指向的内存空间必须是动态申请的，并且 sl 就是指向该
 * 动态内存空间的首地址的时候才能调用本函数。\n
 * 本函数和函数 sllist_alloc_init() 成对使用的。
 * 或者说也可以直接调用函数 free() 来释放函数sllist_alloc_init()
 * 创建的链表头占用的内存空间。
 * @see sllist_alloc_init(), sllist_destroyCallback(), sllist_destroy()
 */
int sllist_free(const SL_LIST *sl)
{
    if (!sl)        return SL_ERR_ARGS;
    if (sl->head)   return SL_ERR_NOTEMPTY;
    free((void *)sl);
    return 0;
}

/**
 * @brief   销毁链表
 * @details 释放链表 sl 中的所有节点。销毁完成后链表 sl 就是一个空链表了。
 * @param [in] sl: 指向链表头的指针
 * @return  none
 * @note
 * 链表 sl 中的所有节点必须都是动态申请的，并且链表中节点的首地址就是
 * 动态申请的内存空间的首地址，才能使用本函数来销毁链表。\n
 * 如果链表 sl 中的所有节点都是动态申请的，但是节点的首地址不是动态
 * 申请的内存空间的首地址，那么请使用函数 sllist_destroyCallback()
 * 来释放节点的内存空间。\n
 * 本函数执行完成之后，链表 sl 就是一个空链表了。
 * @see sllist_destroyCallback()
 */
void sllist_destroy(SL_LIST *sl)
{
    SL_NODE *pNode;
    SL_NODE *tmp;

    if (!sl)    return;

    for (pNode = sl->head; pNode; pNode = tmp)
    {
        tmp = pNode->next;
        free(pNode);
    }
    SLLIST_INIT(sl);
}

/**
 * @brief   销毁链表
 * @details
 * 使用传入的回调函数 callback 来释放链表 sl 中的所有节点。
 * 销毁成功之后，链表 sl 就是一个空链表了
 * @param [in] sl: 指向链表头的指针
 * @param [in] callback: 指向释放链表节点的函数的指针
 * @retval SL_ERR_ARGS: 参数 sl 或 callback 为 NULL
 * @retval 0: 成功
 * @note
 * 在 sl 指向的链表中的所有节点的内存空间都是动态内存空间的时候，
 * 才能调用此函数来销毁链表。
 * @see sllist_destroy()
 */
int32_t sllist_destroyCallback(SL_LIST *sl, sl_trav_callback callback)
{
    SL_NODE *pNode;
    SL_NODE *tmp;

    if (!sl || !callback)   return SL_ERR_ARGS;

    for (pNode = sl->head; pNode; pNode = tmp)
    {
        tmp = pNode->next;
        callback(pNode);
    }
    SLLIST_INIT(sl);
    return 0;
}

/**
 * @brief   判断链表是否为空
 * @details 判断链表是否为空
 * @param [in] sl: 指向链表头的指针
 * @retval  SL_ERR_ARGS: 参数 sl 的值为 NULL
 * @retval  1: 参数 sl 指向的链表为空
 * @retval  0: 参数 sl 指向的链表为非空
 * @note    None.
 */
int32_t sllist_isempty(const SL_LIST *sl)
{
    if (!sl)    return SL_ERR_ARGS;

    if (sl->head)   return 0;

    return 1;
}

/**
 * @brief   获得链表的长度
 * @details 返回链表中节点的数量
 * @param [in] sl: 指向链表头的指针
 * @retval  SL_ERR_ARGS: 参数 sl 为NULL
 * @return  返回链表中节点的数量
 * @note    None.
 */
uint32_t sllist_length(const SL_LIST *sl)
{
    if (!sl)    return (uint32_t)SL_ERR_ARGS;

    return sl->length;
}

/**
 * @brief   从链表头插入一个节点
 * @details 从链表头插入一个节点
 * @param [in] sl: 指向链表头的指针
 * @param [in] node: 指向一个节点的指针
 * @retval  SL_ERR_ARGS: 参数 sl 或 node 的值为 NULL
 * @retval  SL_ERR_ISEXIST: 链表 sl 中存在节点 node
 * @retval  0: 插入节点成功
 * @note    这个新插入的节点 node 就是链表 sl 的头节点。
 * @see sllist_insert_at(), sllist_insert_tail()
 */
int32_t sllist_insert_head(SL_LIST *sl, SL_NODE *node)
{
    if (!sl || !node)   return SL_ERR_ARGS;

    if (sllist_addr2at(sl, node) >= 0)   return SL_ERR_ISEXIST;

    node->next = sl->head;
    sl->head = node;
    sl->length++;
    if (!sl->tail)
        sl->tail = node;

    return 0;
}

/**
 * @brief   从链表尾插入一个节点
 * @details 从链表尾插入一个节点
 * @param [in] sl: 指向链表头的指针
 * @param [in] node: 指向一个节点的指针
 * @retval  SL_ERR_ARGS: 参数 sl 或 node 的值为 NULL
 * @retval  SL_ERR_ISEXIST: 链表 sl 中存在节点 node
 * @retval  0: 插入节点成功
 * @note    这个新插入的节点 node 就是链表 sl 的尾节点。
 * @see sllist_insert_head(), sllist_insert_at()
 */
int32_t sllist_insert_tail(SL_LIST *sl, SL_NODE *node)
{
    if (!sl || !node)    return SL_ERR_ARGS;

    if (sllist_addr2at(sl, node) >= 0)   return SL_ERR_ISEXIST;

    node->next = NULL;
    sl->length++;
    if (sl->tail)
    {
        sl->tail->next = node;
        sl->tail       = node;
    }
    else
    {
        sl->head = node;
        sl->tail = node;
    }

    return 0;
}

/**
 * @brief   从链表指定节点之后插入一个节点
 * @details 从链表 sl 中第 index 个节点之后插入一个节点 node 。
 * @param [in] sl: 指向链表头的指针
 * @param [in] node: 指向一个节点的指针
 * @param [in] index: 指定链表中的节点，从0开始。有效范围：0 ~ 链表长度 - 1
 * @retval  SL_ERR_ARGS: 参数 sl 或 node 的值为 NULL
 * @retval  SL_ERR_ISEXIST: 链表 sl 中存在节点 node
 * @retval  SL_ERR_INDEX: 参数 index 大于链表 sl 的长度
 * @retval  0: 插入节点成功
 * @note
 * 这个新插入的节点 node 是链表 sl 中第 index + 1 个节点。\n
 * 如果链表 ls 为一个空链表，将返回 SL_ERR_INDEX。
 * @see sllist_insert_tail(), sllist_insert_head(), sllist_addr2at()
 */
int32_t sllist_insert_at(SL_LIST *sl, SL_NODE *node, uint32_t index)
{
    uint32_t i;
    SL_NODE *pNode;

    if (!sl || !node)   return SL_ERR_ARGS;

    if (sllist_addr2at(sl, node) >= 0)   return SL_ERR_ISEXIST;

    for (i=0, pNode = sl->head;
         pNode && (i < index);
         pNode = pNode->next, i++) ;

    if (!pNode) return SL_ERR_INDEX;

    sl->length++;
    node->next = pNode->next;
    pNode->next = node;
    return 0;
}

/**
 * @brief   返回链表中一个节点在链表中的索引位置
 * @details 从链表 sl 中找到地址为 node 的节点在链表中的索引位置。
 * @param [in] sl: 指向链表头的指针
 * @param [in] node: 指向一个节点的指针
 * @retval  SL_ERR_ARGS: 参数 sl 或 node 的值为 NULL
 * @retval  SL_ERR_NOTEXIST: 链表 sl 中不存在地址为 node 的节点
 * @return  返回非负数，成功；返回负数失败
 * @note    none
 * @see sllist_insert_at()
 */
int32_t sllist_addr2at(SL_LIST *sl, SL_NODE *node)
{
    int32_t i;
    SL_NODE *pNode;

    if (!sl || !node)   return SL_ERR_ARGS;

    for (i = 0, pNode = sl->head; pNode; pNode = pNode->next, i++)
    {
        if (pNode == node)
            return i;
    }
    return SL_ERR_NOTEXIST;
}

/**
 * @brief   寻找链表中的节点
 * @details 调用回调函数 callback 来遍历链表 sl 中的节点；
 *          如果找到了节点，那么 callback 返回非0，
 *          本函数就会返回该节点的地址。
 * @param [in] sl: 指向链表头的指针
 * @param [in] callback: 用于寻找节点的函数
 * @param [in] arg: 用于回调函数 callback 的第二个参数
 * @return
 * 寻找到了节点返回该节点的地址；\n
 * 没有找到节点或者参数 sl 或 callback 为 NULL 则返回 NULL
 * @note
 * 本函数用于遍历链表 sl 中的节点，
 * 回调函数 callback 用于指定是否找到要寻找的节点。
 * @see sllist_traverse()
 */
SL_NODE *sllist_find(const SL_LIST *sl, sl_match_callback callback, void *arg)
{
    const SL_NODE *pNode;

    if (!sl || !callback)   return NULL;

    SL_FOREACH(pNode, sl)
    {
        if (callback(pNode, arg))   return (SL_NODE *)pNode;
    }

    return NULL;
}

/**
 * @brief   删除链表中节点
 * @details 删除链表 sl 中节点 node
 * @param [in] sl: 指向链表头的指针
 * @param [in] node: 指向节点的指针
 * @retval SL_ERR_ARGS: 参数 sl 或 node 为NULL
 * @retval SL_ERR_ISEMPTY: 链表 sl 为空链表
 * @retval SL_ERR_NOTEXIST: 链表 sl 中没有找到节点 node
 * @retval 0: 成功
 * @note    none
 * @see sllist_deleteAt(), sllist_at()
 */
int32_t sllist_delete(SL_LIST *sl, const SL_NODE *node)
{
    SL_NODE *pNode;
    int32_t ret = SL_ERR_ARGS;

    if (!sl || !node)   goto return_point;

    ret = SL_ERR_NOTEMPTY;
    if (!sl->head)      goto return_point;

    ret = SL_ERR_NOTEXIST;
    pNode = sl->head;
    if (pNode == node)
    {
        if (sl->head == sl->tail)
            sl->tail = sl->tail->next;
        sl->head = sl->head->next;
        ret = 0;
        sl->length--;
        goto return_point;
    }

    for (; pNode; pNode=pNode->next)
    {
        if (pNode->next == node)
        {
            if (pNode->next == sl->tail)
                sl->tail = pNode;
            pNode->next = pNode->next->next;
            ret = 0;
            sl->length--;
            goto return_point;
        }
    }

return_point:
    return ret;
}

/**
**********************************************************************
* @brief    删除链表中指定节点
* @details  删除链表 sl 中第 index 个节点。index的值从0开始
* @param[in] sl: 指向链表头的指针
* @param[in] index:
* 链表中第index个节点，从0开始；范围：0 ~ 链表 sl 长度 - 1
* @return 失败，返回NULL；否则返回被删除的节点的首地址。
* @note
* 返回NULL的情况：
* - sl 为NULL
* - sl 指向的链表为空
* - 没有找到 index 指向的节点
* @see sllist_delete(), sllist_addr2at()
*/
SL_NODE *sllist_deleteAt(SL_LIST *sl, uint32_t index)
{
    SL_NODE *pNode_prev;
    SL_NODE *pNode;
    uint32_t i;
    if (!sl || !sl->head)    return NULL;

    pNode_prev = sl->head;
    if (!index)
    {
        sl->head = pNode_prev->next;
        if (pNode_prev == sl->tail)
            sl->tail = pNode_prev->next;    // NULL
        sl->length--;
        return pNode_prev;
    }

    for (i=1, pNode = pNode_prev->next;
         pNode;
         pNode_prev = pNode, pNode = pNode->next, i++)
    {
        if (i == index)
        {
            if (sl->head == pNode)
                sl->head = pNode->next;
            if (sl->tail == pNode)
                sl->tail = pNode_prev;

            pNode_prev->next = pNode->next;

            sl->length--;
            return pNode;
        }
    }
    return NULL;
}

/**
 * @brief   遍历链表
 * @details 遍历链表 sl 中节点所有节点
 * @param [in] sl: 指向链表头的指针
 * @param [in] callback: 指向回调函数的指针
 * @return  none
 * @note
 * 本函数用于遍历链表 sl 中所有的节点，
 * 并将节点的地址作为参数传递给回调函数 callback。
 * @see sllist_find()
 */
void sllist_traverse(SL_LIST *sl, sl_trav_callback callback)
{
    const SL_NODE *pNode;

    if (!sl || !callback)   return;

    SL_FOREACH(pNode, sl)
        callback(pNode);
}

/**
 * @brief   链表排序
 * @details
 * 链表 sl 排序，排序方式由回调函数 callback 决定。
 * 如果传入回调函数 callback 的两个参数需要交换位置，
 * 那么回调函数 callback 就返回非0，否则返回0。
 * @param [in] sl: 指向链表头的指针
 * @param [in] callback: 指向回调函数的指针
 * @return  none
 * @note    none
 */
void sllist_sort(SL_LIST *sl, sl_sort_callback callback)
{
    SL_NODE *pNode1_prev;
    SL_NODE *pNode1;
    SL_NODE *pNode2_prev;
    SL_NODE *pNode2;
    SL_NODE *tmp;

    if (!sl || !callback || (sl->head == sl->tail))   return;

    for (pNode1_prev = NULL,  pNode1 = sl->head;
         pNode1!=sl->tail;
         pNode1_prev = pNode1, pNode1 = pNode1->next)
    {
        for (pNode2_prev = NULL, pNode2 = pNode1->next;
             pNode2;
             pNode2_prev = pNode2, pNode2 = pNode2->next)
        {
            if (callback(pNode1, pNode2))
            {
                // 更新当前链表的头和尾
                if (pNode1 == sl->head)
                    sl->head = pNode2;
                if (pNode2 == sl->tail)
                    sl->tail = pNode1;

                if (pNode1_prev)
                    pNode1_prev->next = pNode2;

                if (pNode1->next == pNode2)
                {
                    tmp = pNode1;
                }
                else
                {
                    pNode2_prev->next = pNode1;
                    tmp = pNode1->next;
                }
                pNode1->next = pNode2->next;
                pNode2->next = tmp;

                // 恢复原 pNode1 和 pNode2 的位置
                if (pNode1_prev)
                    pNode1 = pNode1_prev->next;
                else
                    pNode1 = sl->head;
                if (pNode2_prev)
                    pNode2 = pNode2_prev->next;
                else
                    pNode2 = pNode1->next;
            }
        }
    }
}

/**
 * @brief   获得指定节点地址
 * @details 获得链表 sl 中第 index 个节点的地址。
 * @param [in] sl: 指向链表头的指针
 * @param [in] index: 第几个节点。有效值范围：0 ~ 链表sl中节点总数 - 1
 * @return  成功则返回节点地址；否则返回NULL
 * @note    none
 * @see sllist_addr2at()
 */
SL_NODE *sllist_at(const SL_LIST *sl, uint32_t index)
{
    SL_NODE       *pNode;
    uint32_t       i;

    for (pNode = sl->head, i=0; pNode; pNode = pNode->next, i++)
    {
        if (i == index)
            return pNode;
    }
    return NULL;
}

/**
 * @brief   倒置链表中的节点顺序
 * @details 倒置链表中的节点顺序
 * @param [in,out] sl: 指向链表头的指针
 * @return  成功则返回0；否则返回负数。
 * @note    none
 */
int32_t sllist_inversion(SL_LIST *sl)
{
    SL_NODE *pNext, *pPrev, *pNode;

    if (!sl)                        return SL_ERR_ARGS;
    else if (sl->head == sl->tail)  return 0;

    for (pPrev = sl->head, pNode = pPrev->next;
         pNode;
         pPrev = pNode, pNode = pNext)
    {
        pNext = pNode->next;
        pNode->next = pPrev;
    }

    sl->tail = sl->head;
    sl->head = pPrev;
    sl->tail->next = NULL;
    return 0;
}



/** defgroup SIGNAL_LINK_LIST_Exported_Functions
 * @}
 */

/** defgroup SIGNAL_LINK_LIST
 * @}
 */


/**   Copyright (C) 2021 wy1107412334@163.com All rights reserved  **/
/****************************** END OF FILE *************************/

